package leetcode_200;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;



/**
 *@author 周杨
 *BinaryTreeLevelOrderTraversal_102 二叉树的层次遍历
 *describe: 用队列 AC 86%
 *2018年5月19日 下午10:01:15
 */
public class BinaryTreeLevelOrderTraversal_102 {
	static class TreeNode{
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode(int x) { val = x; }
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}
	
	public List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> res=new ArrayList<List<Integer>>();
		if(root==null) {
			return res;
		}
		Queue<TreeNode> queue=new LinkedList<TreeNode>();
		queue.add(root);
		while(!queue.isEmpty()) {
			int count=queue.size();
			List<Integer> list=new ArrayList<Integer>();;
			while(count!=0) {
				TreeNode node=queue.poll();
				if(node.left!=null)
					queue.add(node.left);
				if(node.right!=null)
					queue.add(node.right);
				list.add(node.val);
				--count;
			}
			res.add(list);
		}	
		return res;
	}
}
